home *** CD-ROM | disk | FTP | other *** search
/ PD ROM 1 / PD ROM Volume I - Macintosh Software from BMUG (1988).iso / Stacks / Updates⁄New / TEXAS for BMUG / C progs / brwsr.2 ƒ / do_subset.2.c < prev    next >
Encoding:
Text File  |  1987-11-03  |  12.3 KB  |  402 lines  |  [TEXT/KAHL]
  1. /* words to handle subset (proximity filter) tasks....
  2.  * ^z -- 870810-13-....
  3.  *
  4.  * Subset (or subindex) restrictions are useful in doing searches for
  5.  * combinations of terms, phrases, etc., where the terms are themselves
  6.  * common words.  Subsets also become indispensible when working in
  7.  * very large databases, where even slightly-exotic terms occur too many
  8.  * times for convenient browsing through their CONTEXT displays.
  9.  *
  10.  * When a subset has been defined, then instead of showing an INDEX
  11.  * item as something like:
  12.  *      3141 UNIX
  13.  * that item is displayed with a count of how many occurrences are
  14.  * 'valid' in addition to the total number of occurrences:
  15.  *   27/3141 UNIX
  16.  * Thus, in this case only 27 out of the 3141 appearances of the term
  17.  * 'UNIX' happened to be in the neighborhood of the set of words chosen
  18.  * by the user to define the current working subset.
  19.  * 
  20.  * The 'neighborhood' (a half dozen words or so on each side) of a chosen
  21.  * index term is added (logical OR) into the working subset by giving
  22.  * the '&' command when that term's INDEX display is the current item.
  23.  * If a larger neighborhood (half a dozen sentences or so each way) is
  24.  * preferable, use the '&&' command; for a still larger neighborhood
  25.  * (a few paragraphs on each side), use the '&&&' command.
  26.  *
  27.  *
  28.  * IMPLEMENTATION NOTES:
  29.  *
  30.  * Subest searching is handled by an array of flag bits -- one bit
  31.  * for each chunk of NEIGHBORHOOD bytes in the original text.  Bits are
  32.  * held in the array subset[]; they are zero for 'invalid' regions
  33.  * of the original document, and one for 'valid' regions that have
  34.  * been defined by proximity to index terms selected by the user.
  35.  *
  36.  * A value of 32 for NEIGHBORHOOD seems to work very well for defining
  37.  * proximity.  The compression factor from the original document to the
  38.  * array subset[] is NEIGHBORHOOD*8 = 256 in that case.  So, even for a
  39.  * document that is tens of megabytes long, the subset[] array only
  40.  * requires a few hundred kB and it is quite feasible to hold it in
  41.  * memory.
  42.  *
  43.  * The presence of a subset is signalled when the global array pointer
  44.  * 'subset' is non-NULL ... in which case show_current_index_item,
  45.  * make_move, and other words modify their behavior in order to
  46.  * reflect the chosen subset.  If the subset is completely
  47.  * empty, after having just been created or flushed, then the
  48.  * global variable empty_subset is nonzero (true) and short-cuts
  49.  * are taken in counting and displaying words....
  50.  *
  51.  * Consider a single occurrence of a word.  Suppose we want to add the
  52.  * immediate neighborhood of that word to our working subset.  To avoid
  53.  * edge-effects due to the chunkiness of the definition of neighborhood,
  54.  * the routine to set bits in subset[] actually sets 2*WORD_RANGE+1 bits:
  55.  * the bit corresponding to the chunk wherein the chosen word falls,
  56.  * and WORD_RANGE extra bits on each side.
  57.  *
  58.  * Thus, for the choice WORD_RANGE = 1, any index item which is
  59.  * within NEIGHBORHOOD (=32) bytes of our chosen word is certain
  60.  * to be included in the proximity subset; any item which occurs
  61.  * at least 2*NEIGHBORHOOD (=64) bytes away is certain NOT to be
  62.  * included, and items in the intermediate range have a
  63.  * linearly-decreasing probability of false inclusion.  The choice
  64.  * of 32 for NEIGHBORHOOD and 1 for WORD_RANGE therefore gives
  65.  * essentially all items within half a dozen or so words
  66.  * (average word length is 5-6 letters) of the term used to
  67.  * define the subset....
  68.  *
  69.  * In extensive experimentation with the MacForth-based Browser v.244+
  70.  * program on the Macintosh, the above definition of proximity seemed
  71.  * to be by far the most useful one in real life.  It is also quite
  72.  * straightforward to implement with good efficiency.  In addition
  73.  * to the 'word'-neighborhood proximity (within WORD_RANGE chunks),
  74.  * it is occasionally convenient to add a somewhat larger
  75.  * neighborhood to the working subset -- corresponding to proximity
  76.  * within a few sentences or even a few paragraphs.  To do that,
  77.  * the && (sentence-proximity) and &&& (paragraph-proximity) commands
  78.  * simply set more bits on either side of the word's location in
  79.  * subset[].  Specifically, && sets SENTENCE_RANGE bits on each side,
  80.  * and &&& sets PARAGRAPH_RANGE bits on each side.  Values of 10 and 100
  81.  * respectively for those parameters seem to work quite well.
  82.  */
  83.  
  84.  
  85. #include <stdio.h>            /* for FILE, printf(), etc. */
  86. #include <storage.h>        /* for calloc(), free(), etc. */
  87. #include <unix.h>            /* for exit(), etc. */
  88. #include <proto.h>            /* for function prototypes */
  89. #include "brwsr.h"            /* for various definitions */
  90. #include "brwsr.proto.h"    /* for my function prototypes */
  91.  
  92.  
  93. /* Handle the * command to empty out the working subset before
  94.  * beginning to do proximity-filtered searching (that is, to create
  95.  * the array subset[] in empty form). 
  96.  * Also handle the ** command to destroy subset[] (which makes it
  97.  * seem as if it is "full" from the user's viewpoint)
  98.  *
  99.  * Force the user back to INDEX level when the working subindex
  100.  * is emptied or filled, to avoid inconsistencies in moving around
  101.  * the CONTEXT level....
  102.  */
  103.  
  104. void do_make_subset (cmd)
  105.   char cmd[];
  106.   {
  107.     void beep (), create_subset (), destroy_subset (),
  108.             show_current_item ();
  109.     extern int level;
  110.     
  111.     if (cmd[1] == '\0')
  112.         create_subset ();
  113.     else if (cmd[1] == '*')
  114.         destroy_subset ();
  115.     else
  116.         beep ();
  117.     
  118.     level = INDEX;
  119.     show_current_item ();
  120.   }
  121.  
  122.  
  123. /* Do the job of creating the empty array subset[] ... note that if
  124.  * running on a machine with 16-bit int variables such as Lightspeed C
  125.  * on the Mac, the calloc() function won't work for files bigger
  126.  * than 16 MB or so (for NEIGHBORHOOD = 32) ....must modify this
  127.  * to use clalloc(), the non-ANSI standard function for allocating
  128.  * and clearing bigger memory chunks.  Hence, the #ifdef LIGHTSPEED
  129.  * lines below....
  130.  *
  131.  * Note that there is no need to provide a "No file open!" error msg
  132.  * since show_current_item() in calling function will do that for
  133.  * us....
  134.  */
  135.  
  136. void create_subset ()
  137.   {
  138.     extern char* subset;
  139.     extern FILE *doc_file;
  140.     extern int empty_subset;
  141.     extern long max_item[];
  142. #ifdef LIGHTSPEED
  143.     char *clalloc ();
  144. #else
  145.     char *calloc ();
  146. #endif
  147.     void beep (), destroy_subset ();
  148.     
  149.     if (doc_file == NULL)
  150.       return;
  151.  
  152.     destroy_subset ();
  153. #ifdef LIGHTSPEED
  154.     if ((subset = clalloc ((unsigned long)(1 +
  155.             max_item[TEXT]/(NEIGHBORHOOD*8)), (long)sizeof(char))) == NULL)
  156. #else    
  157.     if ((subset = calloc ((unsigned int)(1 +
  158.             max_item[TEXT]/(NEIGHBORHOOD*8)), sizeof(char))) == NULL)
  159. #endif
  160.       {
  161.         beep ();
  162.         printf ("Not enough memory for subset!\n");
  163.         return;
  164.       }
  165.     
  166.     empty_subset = TRUE;
  167.   }
  168.  
  169.  
  170. /* routine to destroy a subset (used in response to a ** command,
  171.  * or when changing over to a new file with a : command, or when about
  172.  * to create a new empty subset inside the * command)
  173.  */
  174.  
  175. void destroy_subset ()
  176.   {
  177.     extern char *subset;
  178.     
  179.     if (subset != NULL)
  180.         free (subset);
  181.     subset = NULL;
  182.   }
  183.  
  184.  
  185. /* routine to invert the working subindex (response to a ~ command) --
  186.  * perform a logical NOT on the entire set, so that what was once a
  187.  * member of the set becomes a non-member, and vice versa....
  188.  *
  189.  * Must set empty_subset FALSE since we don't a priori know that the
  190.  * resulting set is empty or full or what....
  191.  *
  192.  * As with * and ** commands, kick the user back to the INDEX level
  193.  * when this command is executed, for safety's sake....
  194.  */
  195.  
  196. void do_invert_subset ()
  197.   {
  198.       register long i, lim;
  199.     extern char *subset;
  200.     extern long max_item[];
  201.     extern int empty_subset;
  202.     void beep();
  203.  
  204.     if (doc_file == NULL)
  205.       {
  206.         beep ();
  207.         printf ("No file open!\n");
  208.         return;
  209.       }
  210.     if (subset == NULL)
  211.       {
  212.         beep ();
  213.         printf ("No subset!\n");
  214.         return;
  215.       }
  216.  
  217.     lim = max_item[TEXT]/(NEIGHBORHOOD*8);
  218.     for (i = 0; i <= lim; ++i)
  219.         subset[i] = ~subset[i];
  220.  
  221.     empty_subset = FALSE;
  222.     level = INDEX;
  223.     show_current_item ();
  224.   }
  225.   
  226.  
  227. /* handle the '&' command to add the current word's neighborhood to
  228.  * the working subset:
  229.  *    &    adds a few-words neighborhood
  230.  *    &&    adds a few-sentences neighborhood
  231.  *    &&&    adds a few-paragraphs neighborhood
  232.  *
  233.  * Note that instead of calling show_current_item() to finish up
  234.  * this function, since we know that every occurrence of the
  235.  * current item will be in the working subset we can save time
  236.  * and avoid re-counting them all ... hence, the final lines
  237.  * of this routine
  238.  */
  239.  
  240. void do_add_neighborhood (cmd)
  241.   char cmd[];
  242.   {
  243.     int nsize;
  244.     extern int level;
  245.     extern char *subset;
  246.     extern FILE *doc_file, *notes_file;
  247.     void beep (), set_neighborhood_bits (), get_key_rec ();
  248.     extern KEY_REC this_rec, prev_rec;
  249.     extern long current_item[], subset_rec_count;
  250.  
  251.     if (doc_file == NULL)
  252.       {
  253.         beep ();
  254.         printf ("No file open!\n");
  255.         return;
  256.       }
  257.     if (subset == NULL)
  258.       {
  259.         beep ();
  260.         printf ("No subset!\n");
  261.         return;
  262.       }
  263.  
  264.     nsize = WORD_RANGE;
  265.     if (cmd[1] == '&')
  266.       {
  267.         nsize = SENTENCE_RANGE;
  268.         if (cmd[2] == '&')
  269.             nsize = PARAGRAPH_RANGE;
  270.       }
  271.     
  272.     level = INDEX;
  273.     set_neighborhood_bits (nsize);
  274.     empty_subset = FALSE;
  275.     get_key_rec (&prev_rec, current_item[INDEX] - 1);
  276.     get_key_rec (&this_rec, current_item[INDEX]);
  277.     subset_rec_count = this_rec.ccount - prev_rec.ccount;
  278.     printf ("%6ld/%-6ld %.28s\n", subset_rec_count, subset_rec_count,
  279.                 this_rec.kkey);
  280.     if (notes_file != NULL)
  281.         fprintf (notes_file, "%6ld/%-6ld %.28s\n", subset_rec_count,
  282.                     subset_rec_count, this_rec.kkey);
  283.   }
  284.  
  285.  
  286. /* function to set n bits on each side of each current index term in the
  287.  * subset[] array ... note that it is important to set min_item[CONTEXT]
  288.  * and max_item[CONTEXT] values before using them, since they are only
  289.  * set ordinarily when descending ('=' command) into the CONTEXT level...
  290.  * values of prev_rec and this_rec are set every time an index item
  291.  * is displayed, so they will be all right for us already....
  292.  */
  293.  
  294. void set_neighborhood_bits (n)
  295.   register int n;
  296.   {
  297.     register long i;
  298.     register PTR_REC j, j0, j1;
  299.     extern long min_item[], max_item[];
  300.     extern KEY_REC prev_rec, this_rec;
  301.     PTR_REC get_ptr_rec ();
  302.     void set_subset_bit ();
  303.     
  304.     min_item[CONTEXT] = prev_rec.ccount;
  305.     max_item[CONTEXT] = this_rec.ccount - 1;
  306.     
  307.     if ((this_rec.ccount-prev_rec.ccount) * n > GIVE_WARNING)
  308.         printf ("Please wait (%ld bits to set)...\n",
  309.             (this_rec.ccount - prev_rec.ccount) * n * 2 + 1);
  310.  
  311.     for (i = min_item[CONTEXT]; i <= max_item[CONTEXT]; ++i)
  312.       {
  313.         j = get_ptr_rec (i);
  314.         j0 = j - n * NEIGHBORHOOD;
  315.         if (j0 < min_item[TEXT])
  316.             j0 = min_item[TEXT];
  317.         j1 = j + n * NEIGHBORHOOD;
  318.         if (j1 > max_item[TEXT])
  319.             j1 = max_item[TEXT];
  320.         for (j = j0; j <= j1; j += NEIGHBORHOOD)
  321.             set_subset_bit (j);
  322.       }
  323.   }
  324.  
  325.  
  326. /* function to set a bit in the array subset[] for a chosen character
  327.  * offset from the start of the file ... just convert the offset into
  328.  * byte and bit numbers and then "OR" the 1 into that slot....
  329.  *
  330.  * (An attempt to optimize for the specific value NEIGHBORHOOD = 32,
  331.  * using & and >> in place of % and /, did not yield a significant
  332.  * improvement in speed... ^z 870813)
  333.  */
  334.  
  335. void set_subset_bit (offset)
  336.   long offset;
  337.   {
  338.     int bit_no;
  339.     long byte_no;
  340.     extern char *subset;
  341.  
  342.     bit_no = (offset % (8 * NEIGHBORHOOD)) / NEIGHBORHOOD;
  343.     byte_no = offset / (8 * NEIGHBORHOOD);
  344.     
  345.     subset[byte_no] |= 1 << bit_no;
  346.   }
  347.  
  348.  
  349. /* function to return the value of a bit in the array subset[] for a
  350.  * chosen character offset from the start of the document file ...
  351.  * as in set_subset_bit() above, just convert offset into byte and
  352.  * bit numbers, extract the relevant bit, shift it down, and return
  353.  * it....
  354.  *
  355.  * (An attempt to optimize for the specific value NEIGHBORHOOD = 32,
  356.  * using & and >> in place of % and /, did not yield a significant
  357.  * improvement in speed... ^z 870813)
  358.  */
  359.  
  360. int get_subset_bit (offset)
  361.   long offset;
  362.   {
  363.     int bit_no;
  364.     long byte_no;
  365.     extern char *subset;
  366.  
  367.     bit_no = (offset % (8 * NEIGHBORHOOD)) / NEIGHBORHOOD;
  368.     byte_no = offset / (8 * NEIGHBORHOOD);
  369.  
  370.     return ((subset[byte_no] >> bit_no) & 1);
  371.   }
  372.  
  373.  
  374. /* function to count and return the number of occurrences of this_rec
  375.  * in the working subindex (i.e., the number of times the word comes
  376.  * up with its subset[] bit turned ON) ....
  377.  */
  378.  
  379. long count_subset_recs (this_recp, prev_recp)
  380.   KEY_REC *this_recp, *prev_recp;
  381.   {
  382.     register long i, n;
  383.     extern int empty_subset;
  384.     PTR_REC get_ptr_rec ();
  385.     int get_subset_bit ();
  386.     
  387.     if (empty_subset)
  388.         return (0L);
  389.  
  390.     if (this_recp->ccount - prev_recp->ccount > GIVE_WARNING)
  391.         printf ("Please wait (%ld words to check)...\n",
  392.                     this_recp->ccount - prev_recp->ccount);
  393.     
  394.     for (n = 0, i = prev_recp->ccount; i < this_recp->ccount; ++i)
  395.         n += get_subset_bit ((long)get_ptr_rec (i));
  396.     
  397.     return (n);
  398.   }
  399.  
  400.  
  401.  
  402.